package com.gxc.linkedList;

/**
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class SortList {

    public static void main(String[] args) {
        ListNode head1 = new ListNode(4);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(1);
        ListNode head4 = new ListNode(3);
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;

        ListNode listNode = sortList3(head1);
        System.out.println("");
    }

    public static ListNode sortList(ListNode head) {
        ListNode hair = new ListNode(0);
        hair.next = head;

        ListNode prev = hair;
        ListNode cur = head;
        while (cur != null) {
            ListNode tail = cur;
            ListNode min = cur;
            ListNode exchange = cur;
            ListNode minPrev = prev;
            while (tail.next != null) {
                if (tail.next.val < min.val) {
                    minPrev = tail;
                    min = tail.next;
                }
                tail = tail.next;
            }
            if (exchange != min) {
                prev.next = min;
                ListNode minNext = min.next;
                if (min!=exchange.next) min.next = exchange.next;
                else min.next = exchange;
                exchange.next = minNext;
                if (minPrev!=exchange) minPrev.next = exchange;
            }
            prev = min;
            cur = min.next;
        }

        return hair.next;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode sortList2(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) return head;
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast!=tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) fast = fast.next;
        }

        ListNode mid = slow;
        ListNode left = sortList(head, mid);
        ListNode right = sortList(mid, tail);
        ListNode sorted = merge(left, right);
        return sorted;
    }

    public static ListNode merge(ListNode left, ListNode right) {
        ListNode prev = new ListNode(0);
        ListNode temp = prev, temp1 = left, temp2 = right;
        while (temp1 != null && temp2 != null) {
            if (temp1.val < temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) temp.next = temp1;
        if (temp2 != null) temp.next = temp2;
        return prev.next;
    }

    public static ListNode sortList3(ListNode head) {
        if (head == null) {
            return head;
        }
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        ListNode dummyHead = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode prev = dummyHead, curr = dummyHead.next;
            while (curr != null) {
                ListNode head1 = curr;
                for (int i = 1; i < subLength && curr.next != null; i++) {
                    curr = curr.next;
                }
                ListNode head2 = curr.next;
                curr.next = null;
                curr = head2;
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
                    curr = curr.next;
                }
                ListNode next = null;
                if (curr != null) {
                    next = curr.next;
                    curr.next = null;
                }
                ListNode merged = merge(head1, head2);
                prev.next = merged;
                while (prev.next != null) {
                    prev = prev.next;
                }
                curr = next;
            }
        }
        return dummyHead.next;
    }

}